package com.xjl.everyinterview.datastructureandalgorithm.datastructure.binarytree;

import java.util.LinkedList;

/**
 * @author xjl
 * @description: 递归实现 --- 二叉树
 * @date: 2021/8/16 18:24
 **/
public class RecursionBinaryTreeImpl implements BinaryTreeI {

    /**
     * 递归思路
     * 1 如果链表为空就返回
     * 2 取出第一个节点保存到临时变量并删除list第一个数据
     * 3 如果等于null 就返回表示插入问题
     * 4 放入数据  左右递归
     *
     * @param inputList
     * @return
     */
    @Override
    public TreeNode createBinaryTree(LinkedList<Integer> inputList) {

        if (inputList == null || inputList.isEmpty()) {
            return null;
        }
        TreeNode node = null;
        //每次进来弹出一个元素
        Integer data = inputList.removeFirst();
        if (data != null) {
            //将弹出的元素放入到data里
            node = new TreeNode(data);
            //递归弹出的元素放入左节点的data并赋值给node的左指针
            node.leftNode = createBinaryTree(inputList);
            //递归弹出的元素放入右节点的data并赋值给node的右指针
            node.rightNode = createBinaryTree(inputList);
        }
        return node;
    }

    @Override
    public void preOrderTraveral(TreeNode node) {
        if(node == null){
            return;
        }
        System.out.println(node.data);
        inOrderTraveral(node.leftNode);
        inOrderTraveral(node.rightNode);
    }

    /**
     * 二叉树中序遍历
     * 思路 递归
     * 1 如果没有就是返回
     * 2 非空左右递归
     * @param node
     */
    @Override
    public void inOrderTraveral(TreeNode node) {
        if(node == null){
            return;
        }
        inOrderTraveral(node.leftNode);
        System.out.println(node.data);
        inOrderTraveral(node.rightNode);
    }

    @Override
    public void postOrderTraveral(TreeNode node) {
        if(node == null){
            return;
        }
        inOrderTraveral(node.leftNode);
        inOrderTraveral(node.rightNode);
        System.out.println(node.data);
    }

}
